package interview;

public class lc209 {
    public static void main(String[] args) {
        System.out.println(minSubArrayLen2(7, new int[]{2,3,1,2,4,3}));
        System.out.println(minSubArrayLen2(2, new int[]{1,4,4}));
    }
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        /**
         * 双指针
         */
        int left = 0, right = 0;
        int sum = 0;
        int re = Integer.MAX_VALUE;
        for (; right < n; right++) {
            sum += nums[right];
            while(sum >= target){
                re = Math.min(re, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return re == Integer.MAX_VALUE ? 0 : re;
    }

    //二分法 + 前缀和
    public static int minSubArrayLen2(int target, int[] nums) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        //用来记录前n项和
        int[] sums = new int[n];
        sums[0] = nums[0];
        for (int i = 1; i < n; i++){
            sums[i] = sums[i - 1] + nums[i];
        }
        //现在问题转化为寻找 sum[j] - sum[i] >= target 的最小的 j - i
        //即求 sum[j] >= sum[i] + target,这样可以二分
        for (int i = 0; i < n; i++) {
            int l = i, r = n - 1;
            //记录寻找到的下标
            int index = -1;
            //二分查找
            while (l <= r){
                int mid = l +  (r - l) / 2;
                if(sums[mid] == sums[i] + target){
                    index = mid;
                    break;
                }
                else if(sums[mid] < sums[i] + target)
                    l = mid + 1;
                else  r = mid - 1;
            }
            //判断是否找到
            index = l;
            if(index < 0 || index < i)
                continue;
            ans = Math.min(ans, index - i + 1);
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
